package codeRandomThoughts.Test332重新安排行程;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    List<String> path = new ArrayList<>();
    List<List<String>> result = new ArrayList<>();
    boolean[] used = new boolean[301];

    public List<String> findItinerary(List<List<String>> tickets) {
        //首先对输入数据进行排序
        tickets.sort((t1, t2) -> {
            if (t1.get(0).compareTo(t2.get(0)) == 0) {
                return t1.get(1).compareTo(t2.get(1));
            } else {
                return t1.get(0).compareTo(t2.get(0));
            }
        });
        path.add("JFK");
        backtracking(tickets, "JFK");
        return result.get(0);
    }

    public void backtracking(List<List<String>> tickets, String startPos) {
        //终止条件
        if (path.size() == tickets.size() + 1) {
            result.add(new ArrayList<>(path));
            return;
        }else if (!result.isEmpty()){
            return;
        }

        //单层搜索逻辑
        //同时要保证不能死循环,用过的机票不能重复使用,一条路径上不行
        for (int i = 0; i < tickets.size(); i++) {
            List<String> ticket = tickets.get(i);
            if (!used[i] && ticket.get(0).equals(startPos)) {
                path.add(ticket.get(1));
                used[i] = true;
                backtracking(tickets, ticket.get(1));
                used[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }


}
